// LeetCode 主站 Problem Nr. 22: 括号生成

/*
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
	输入：n = 3
	输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
	输入：n = 1
	输出：["()"]

提示：
    1 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import "fmt"

func generateParenthesis(n int) []string {
	return method1(n)
}

// 基于回溯的解法
func method1(n int) []string {
	result := make([]string, 0)
	combine := make([]byte, 2*n)

	var backtracking func(index int, bracket byte)
	backtracking = func(index int, bracket byte) {
		combine[index] = bracket
		if index == len(combine)-1 {
			if checkCombine(combine) {
				result = append(result, string(combine))
			}
			return
		}

		backtracking(index+1, '(')
		backtracking(index+1, ')')
	}

	backtracking(0, '(')
	return result
}

func checkCombine(combine []byte) bool {
	stack := make([]byte, 0)
	for _, b := range combine {
		if b == '(' {
			stack = append(stack, b)
		}

		if b == ')' {
			if len(stack) > 0 && stack[len(stack)-1] == '(' {
				stack = stack[:len(stack)-1]
			} else {
				stack = append(stack, b)
			}
		}
	}
	return len(stack) == 0
}

func main() {
	for i := 1; i <= 8; i++ {
		fmt.Println(len(generateParenthesis(i)))
	}
}
